#ifndef INTERPOLATIONSEARCH_H
#define INTERPOLATIONSEARCH_H

#include "searchalgorithm.h"

// 插值查找类，实现 SearchAlgorithm 接口
// 插值查找适用于数据值分布较均匀的场景，估算目标可能出现的位置以加快查找
class InterpolationSearch : public SearchAlgorithm {
public:
    // 构造函数，接收待查找数据（会内部排序）
    InterpolationSearch(const QVector<int>& values);

    // 执行一次插值查找步骤
    void step() override;

    // 判断查找是否结束
    bool isFinished() const override;

    // 获取当前可视化数据（包含颜色信息）
    const QVector<SortBar>& getData() const override;

    // 设置查找目标值
    void setTarget(int value) override;

    // 是否找到目标值
    bool isFound() const override;

    // 如果找到目标，返回其索引位置
    int getFoundIndex() const override;

    // 返回该查找算法的描述信息（适用于 UI 说明）
    QString getDescription() const override;

    // 获取并清空本次步骤的比较计数
    int getAndResetCompareCount() override;

private:
    QVector<SortBar> bars;  // 存储要查找的数据及颜色
    int low, high;          // 当前查找区间的左右边界
    int pos;                // 当前估算位置
    int target;             // 要查找的目标值
    bool found;             // 是否查找成功
    bool finished;          // 查找是否完成
    int foundIndex;         // 查找到的索引
    int compareCount;       // 本次查找步骤的比较计数
};

#endif // INTERPOLATIONSEARCH_H
